Texture mapping generally refers to mapping information onto a surface of a three-dimensional mesh (i.e., collection of vertices, edges, and faces defining a shape of a three-dimensional object in computer graphics). Texture mapping is typically used in computer graphics to assign information, such as coloring, patterning, and/or lighting, to the surface of a three-dimensional mesh. Preparing a mesh for texture mapping is typically performed in two stages. The first stage is parameterization where a mesh is divided into segments that can be unfolded into the two-dimensional domain with minimal distortion. Thus, this first stage results in a mesh being split into one or more mesh segments. Such mesh segments are three-dimensional portions of the overall mesh; these three-dimensional mesh segments can be flattened into two-dimensional shapes known as texture charts. The second stage is then individually parameterizing the two-dimensional texture charts.
During the second stage parameterization, an important step is placing and orienting the texture charts into a texture atlas as compactly as possible. A texture atlas is a large image containing a collection, or “atlas,” of sub-images, where the sub-images are texture charts of some portion of a three-dimensional mesh. A texture atlas most commonly covers a square or rectangular domain which corresponds to locations in a rectangular pixel image. This allows pixel data to be conveniently stored in memory, while also leveraging commonly used formats such as JPEG, PNG or GIF. The mapping or atlas describes how this two-dimensional image of pixel information appears on the surface of the three-dimensional shape.
Currently, to pack texture charts into a texture atlas, one approach approximates each two-dimensional texture chart utilizing a rectangular bounding box. The rectangular bounding boxes are then packed into a texture atlas. However, this approach does not take into account that texture charts often have arbitrary shapes. As such, representing texture charts with a bounding box can result in wasting unused space thereby creating a larger than necessary texture atlas. Other approaches use Euclidean distance, or straight-line distance, minimization between the boundary of a newly incorporated texture chart and the boundary of texture charts previously incorporated into a texture atlas as a primary criterion for placing a texture chart. For example, in one method, texture charts are placed using a minimum distance between the bottom boundary of the texture chart being placed into the texture atlas and the top boundary of the texture atlas. Other methods build on this approach by sampling multiple orientations of a texture chart and choosing the orientation for placing the texture chart to minimize unused space. Further methods implement sampling placements of a texture chart from four different sides (top, bottom, left, and right) instead of only placing the texture chart from the top. Still further, other methods add a texture chart from all four sides and allow the texture chart to wrap around the atlas boundary. However, each of these methods utilizing Euclidean distance minimization, or straight-line distance, results in unused space within a texture atlas and, accordingly, does not provide optimal packing.